This paper is dedicated to the study of properties of the operations ∪ and ∩ in the upper semilattice of the e-degrees as well as in the interval (c,c') e for any e-degree c.

It is shown that for every (Turing) degree 0 < a < 0´ there is a minimal degree m < 0´ such that a ∨ m = 0´ (and therefore a ∧ m = 0).

Jockusch showed that 2-generic degrees are downward dense below a 2-generic degree. That is, if a is 2-generic, and $0 < {\bf{b}} < {\bf{a}}$, then there is a 2-generic g with $0 < {\bf{g}} < {\bf{b}}.$ In the case of 1-generic degrees Kumabe, and independently Chong and Downey, constructed a minimal degree computable from a 1-generic degree. We explore the tightness of these results.We solve a question of Barmpalias and Lewis-Pye by constructing a minimal degree (...) computable from a weakly 2-generic one. While there have been full approximation constructions of ${\rm{\Delta }}_3^0$ minimal degrees before, our proof is rather novel since it is a computable full approximation construction where both the generic and the minimal degrees are ${\rm{\Delta }}_3^0 - {\rm{\Delta }}_2^0$. (shrink)

A computably enumerable degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC, (...) and show that there exists a minimal pair which join to a plus cupping degree, so that PC ⊈ NB. This gives a first known difference between NB and PC. (shrink)

Lachlan [9] proved that there exists a non-recursive recursively enumerable degree such that every non-recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a0, a1 such that for every non-recursive r. e. degree w, there is a pair of incomparable r. e. degrees b0, b2 such (...) that w = b0 V b1 and bi for i = 0, 1. (shrink)

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies [14] and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes (...) induced by ≤LK are called LK degrees and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity. We show that with respect to ≤LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications. (shrink)

In "Bounding minimal degrees by computably enumerable degrees" by A. Li and D. Yang, (this Journal, [1998]), the authors prove that there exist non-computable computably enumerable degrees c > a > 0 such that any minimal degree m being below c is also below a. We analyze the proof of their result and show that the proof contains a mistake. Instead we give a proof for the opposite result.

We prove a number of results in effective randomness, using methods in which Π⁰₁ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.

We consider the set of jumps below a Turing degree, given by JB={x':x≤a}, with a focus on the problem: Which recursively enumerable degrees a are uniquely determined by JB? Initially, this is motivated as a strategy to solve the rigidity problem for the partial order R of r.e. degrees. Namely, we show that if every high2 r.e. degree a is determined by JB, then R cannot have a nontrivial automorphism. We then defeat the strategy—at least in the (...) form presented—by constructing pairs a0, a1 of distinct r.e. degrees such that JB=JB within any possible jump class {x:x'=c}. We give some extensions of the construction and suggest ways to salvage the attack on rigidity. (shrink)

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a (...) low c.e. degree isolating a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 259–266]; there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 31–51]. (shrink)

Cooper proved in [S.B. Cooper, Strong minimal covers for recursively enumerable degrees, Math. Logic Quart. 42 191–196] the existence of a c.e. degree with a strong minimal cover . So is the greastest c.e. degree below . Cooper and Yi pointed out in [S.B. Cooper, X. Yi, Isolated d.r.e. degrees, University of Leeds, Dept. of Pure Math., 1995. Preprint] that this strongly minimal cover cannot be d.c.e., and meanwhile, they proposed the notion of isolated (...) degrees: a d.c.e. degree is isolated by a c.e. degree if is the greatest c.e. degree below , and we also say that isolates . In [G. Wu, Bi-isolation in the d.c.e. degrees, J. Symbolic Logic 69 409–420], Wu extended Cooper–Yi’s notion and proved that there are intervals of d.c.e. degrees containing exactly one c.e. degree . Following Cooper and Yi’s notion, is called a bi-isolating degree. The bi-isolating degrees are dense in the high c.e. degrees. Arslanov asked whether the bi-isolating degrees occur in every jump class. In this paper, we prove that there are low bi-isolating degrees, providing a partial solution to Arslanov’s question. (shrink)

In this paper we will study four forcing notions, two of them giving a minimal degree of constructibility. These constructions give answers to questions in [Ih].

For the purposes of this monograph, "by a degree" is meant a degree of recursive unsolvability. A degree [script bold]m is said to be minimal if 0 is the unique degree less than [script bold]m. Each of the six chapters of this self-contained monograph is devoted to the proof of an existence theorem for minimal degrees.

We answer a question of Jockusch by constructing a hyperimmune-free minimal degree below a 1-generic one. To do this we introduce a new forcing notion called arithmetical Sacks forcing. Some other applications are presented.

We formulate an abstract version of the finite injury method in the form of the Baire category theorem. The theorem has the following corollaries: The Friedberg-Muchnik pair of recursively enumerable degrees, the Sacks splitting theorem, the existence of a minimal degree below 0′ and the Shoenfield jump theorem.

We prove two antibasis theorems for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} classes. The first is a jump inversion theorem for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} classes with respect to the global structure of the Turing degrees. For any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P\subseteq 2^\omega}$$\end{document}, define S(P), the degree spectrum of P, to be the set of all Turing degrees a such (...) that there exists \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A \in P}$$\end{document} of degree a. For any degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document}, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}^{-1}({\bf a) = \{b : b' = a \}}}$$\end{document}. We prove that, for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document} and any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class P, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}^{-1} ({\bf a}) \subseteq S(P)}$$\end{document} then P contains a member of every degree. For any degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document} such that a is recursively enumerable (r.e.) in 0', let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${Jump_{\bf \leq 0'} ^{-1}({\bf a)=\{b : b \leq 0' \textrm{and} b' = a \}}}$$\end{document}. The second theorem concerns the degrees below 0'. We prove that for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a\geq 0'}}$$\end{document} which is recursively enumerable in 0' and any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class P, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}_{\bf \leq 0'} ^{-1}({\bf a)} \subseteq S(P)}$$\end{document} then P contains a member of every degree. (shrink)

Grigorieff showed that forcing to add a subset of ω using partial functions with suitably chosen domains can add a generic real of minimal degree. We show that forcing with partial functions to add a subset of an uncountable κ without adding a real never adds a generic of minimal degree. This is in contrast to forcing using branching conditions, as shown by Brown and Groszek.

We consider a well-known partial order of Prikry for producing a collapsing function of minimal degree. Assuming MA + ≠ CH, every new real constructs the collapsing map.

We study generalizations of shortest programs as they pertain to Schaefer’s problem. We identify sets of -minimal and -minimal indices and characterize their truth-table and Turing degrees. In particular, we show , , and that there exists a Kolmogorov numbering ψ satisfying both and . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, , is 2-c.e. but not co-2-c.e. Some open problems (...) are left for the reader. (shrink)

In the study of the arithmetic degrees the $\omega \text {-REA}$ sets play a role analogous to the role the r.e. degrees play in the study of the Turing degrees. However, much less is known about the arithmetic degrees and the role of the $\omega \text {-REA}$ sets in that structure than about the Turing degrees. Indeed, even basic questions such as the existence of an $\omega \text {-REA}$ set of minimal arithmetic degree are (...) open. This paper makes progress on this question by demonstrating that some promising approaches inspired by the analogy with the r.e. sets fail to show that no $\omega \text {-REA}$ set is arithmetically minimal. Finally, it constructs a $\prod ^0_{2}$ singleton of minimal arithmetic degree. Not only is this a result of considerable interest in its own right, constructions of $\prod ^0_{2}$ singletons often pave the way for constructions of $\omega \text {-REA}$ sets with similar properties. Along the way, a number of interesting results relating arithmetic reducibility and rates of growth are established. (shrink)

It is shown that the nonrecursive predecessors of a 1-generic degree $ are all 1-generic. As a corollary, it is shown that the 1-generic degrees are not densely ordered.

In this paper, we prove that there exist computably enumerable degrees a and b such that $\mathbf{a} > \mathbf{b}$ and for any degree x, if x ≤ a and x is a minimal degree, then $\mathbf{x}.

Theorem. There is a non-empty Π10 class of reals, each of which computes a real of minimal degree. Corollary. WKL “there is a minimal Turing degree”. This answers a question of H. Friedman and S. Simpson.

MOTIVATION The constructivization of ; => D(_£^') poses several problems. For some of these the tools of MD can be modified; for others new methods will need to be established. What must we do to make a full approximation to ; * D? We ...

If X0and X1are both generic, the theories of the degrees below X0and X1are the same. The same is true if both are random. We show that then-genericity orn-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

We construct a high c.e. degree which is not the join of two minimal degrees and so refute Posner's conjecture that every high c.e. degree is the join of two minimal degrees. Additionally, the proof shows that there is a high c.e. degree a such that for any splitting of a into degrees b and c one of these degrees bounds a 1-generic degree.

We develop a new method for constructing hyperimmune minimal degrees and construct an ANR degree which is a minimal cover of a minimal degree.

This paper describes and defends the view that minimal chemical life essentially involves the chemical integration of three chemical functionalities: containment, metabolism, and program (Rasmussen et al. in Protocells: bridging nonliving and living matter, 2009a ). This view is illustrated and explained with the help of CMP and Rasmussen diagrams (Rasmussen et al. In: Rasmussen et al. (eds.) in Protocells: bridging nonliving and living matter, 71–100, 2009b ), both of which represent the key chemical functional dependencies among containment, metabolism, (...) and program. The CMP model of minimal chemical life gains some support from the broad view of life as open-ended evolution, which I have defended elsewhere (Bedau in The philosophy of artificial life, 1996 ; Bedau in Artificial Life, 4:125–140, 1998 ). Further support comes from the natural way the CMP model resolves the puzzle about whether life is a matter of degree. (shrink)

Using a Levy hierarchy and a fine structure theory for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${K(\mathbb{R})}$$\end{document}, we obtain scales of minimal complexity in this inner model. Each such scale is obtained assuming the determinacy of only those sets of reals whose complexity is strictly below that of the scale constructed.

We extend Meyer's 1972 investigation of sets of minimal indices. Blum showed that minimal index sets are immune, and we show that they are also immune against high levels of the arithmetic hierarchy. We give optimal immunity results for sets of minimal indices with respect to the arithmetic hierarchy, and we illustrate with an intuitive example that immunity is not simply a refinement of arithmetic complexity. Of particular note here are the fact that there are three (...) class='Hi'>minimal index sets located in Π3 − Σ3 with distinct levels of immunity and that certain immunity properties depend on the choice of underlying acceptable numbering. We show that minimal index sets are never hyperimmune; however, they can be immune against the arithmetic sets. Lastly, we investigate Turing degrees for sets of random strings defined with respect to Bagchi's size-function s. (shrink)